/**********************************************************************
 *
 * PostGIS - Spatial Types for PostgreSQL
 * http://postgis.net
 *
 * Copyright 2011 Sandro Santilli <strk@kbt.io>
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU General Public Licence. See the COPYING file.
 *
 **********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CUnit/Basic.h"

#include "liblwgeom_internal.h"
#include "lwgeodetic.h"
#include "lwgeodetic_tree.h"
#include "intervaltree.h"
#include "cu_tester.h"


static void test_tree_circ_create(void)
{
	LWLINE *g;
	CIRC_NODE *c;
	/* Line with 4 edges */
	g = lwgeom_as_lwline(lwgeom_from_wkt("LINESTRING(0 88,0 89,0 90,180 89,180 88)", LW_PARSER_CHECK_NONE));
	c = circ_tree_new(g->points);
	//circ_tree_print(c, 0);

	if ( CIRC_NODE_SIZE > 4 )
	{
		CU_ASSERT(c->num_nodes == 4);
	}
	else
	{
		CU_ASSERT(c->num_nodes  == ( 4 % CIRC_NODE_SIZE ? 1 : 0 ) + 4 / CIRC_NODE_SIZE);
	}

	circ_tree_free(c);
	lwline_free(g);
}


static void test_tree_circ_pip(void)
{
	LWLINE *g;
	CIRC_NODE *c;
	POINT2D pt, pt_outside;
	int rv, on_boundary;

	pt.x = 0.0;
	pt.y = 0.0;
	pt_outside.x = -2.0;
	pt_outside.y = 0.0;

	/* Point in square */
	g = lwgeom_as_lwline(lwgeom_from_wkt("LINESTRING(-1 -1,1 -1,1 1,-1 1,-1 -1)", LW_PARSER_CHECK_NONE));
	c = circ_tree_new(g->points);
	rv = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv, 1);

	/* Point on other side of square */
	pt.x = 2.0;
	pt.y = 0.0;
	rv = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv, 0);

	/* Clean and do new shape */
	circ_tree_free(c);
	lwline_free(g);

	/* Point in square, stab passing through vertex */
	pt.x = 0.0;
	pt.y = 0.0;
	g = lwgeom_as_lwline(lwgeom_from_wkt("LINESTRING(-1 -1,0 -1,1 -1,1 0,1 1,0 1,-1 1,-1 0,-1 -1)", LW_PARSER_CHECK_NONE));
	c = circ_tree_new(g->points);
	//circ_tree_print(c, 0);
	rv = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv, 1);

	/* Point on other side of square, stab passing through vertex */
	pt.x = 2.0;
	pt.y = 0.0;
	rv = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv, 0);

	/* Clean and do new shape */
	circ_tree_free(c);
	lwline_free(g);

	/* Point outside "w" thing, stab passing through vertices and grazing pointy thing */
	pt.x = 2.0;
	pt.y = 0.0;
	g = lwgeom_as_lwline(lwgeom_from_wkt("LINESTRING(-1 -1,0 -1,1 -1,1 0,1 1,0 0,-1 1,-1 0,-1 -1)", LW_PARSER_CHECK_NONE));
	c = circ_tree_new(g->points);
	//circ_tree_print(c, 0);
	rv = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	//printf("rv %d\n", rv);
	CU_ASSERT_EQUAL(rv, 0);

	/* Point inside "w" thing, stab passing through vertices and grazing pointy thing */
	pt.x = 0.8;
	pt.y = 0.0;
	rv = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	//printf("rv %d\n", rv);
	CU_ASSERT_EQUAL(rv, 1);

	/* Clean and do new shape */
	circ_tree_free(c);
	lwline_free(g);

}

static void test_tree_circ_pip2(void)
{
	LWGEOM* g;
	LWPOLY* p;
	LWPOINT* lwpt;
	int rv_classic, rv_tree, on_boundary;
	POINT2D pt, pt_outside;
	GBOX gbox;
	CIRC_NODE *c;

	g = lwgeom_from_wkt("POLYGON((0 0,0 1,1 1,1 0,0 0))", LW_PARSER_CHECK_NONE);
	p = lwgeom_as_lwpoly(g);

	pt.x = 0.2;
	pt.y = 0.1;
	lwgeom_calculate_gbox_geodetic(g, &gbox);
	gbox_pt_outside(&gbox, &pt_outside);
	c = circ_tree_new(p->rings[0]);
	//circ_tree_print(c, 0);
	rv_classic = lwpoly_covers_point2d(p, &pt);
	rv_tree = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv_tree, rv_classic);
	circ_tree_free(c);
	lwgeom_free(g);

	g = lwgeom_from_hexwkb("0103000020E6100000010000004700000000000000621119C000000040C70C4B40000000E0CC6C18C0000000A026FF4A4000000040438519C000000000E8F44A40000000000F5318C00000004024C84A4000000060F9E518C0000000A027AD4A40000000805E0D18C0000000C0F5784A4000000040539718C000000080815E4A40000000C026FE19C0000000C0502D4A4000000060127019C000000040EA164A40000000003BFD1BC0000000609E234A4000000080D9011CC000000060B9114A4000000040C8501EC0000000C0D50C4A40000000C05F2C20C000000040C9E749400000006008D820C000000080D6F0494000000080139F20C000000060F3DE4940000000A0B16421C0000000C059C94940000000808FA223C0000000C007B949400000000041E722C000000080C3DC4940000000808F4224C0000000405DCE494000000060752923C000000040A9EF4940000000005CAD24C0000000C036E4494000000040F88624C00000008078FE494000000060558523C00000006025134A40000000403AED24C00000000011174A40000000A05E7D23C0000000E0A41F4A4000000040F0AD23C0000000809A304A4000000040A64E23C000000040C9474A40000000C0FCA221C0000000C030554A40000000805EDD23C0000000E010474A4000000040BFF822C00000008078664A4000000080C98F22C000000040E2914A40000000C036E021C00000002024924A4000000080D9E121C000000000D0A14A4000000040533723C000000040B99D4A40000000204B1E23C0000000C0CCB04A4000000000625A24C0000000A071B44A40000000004A5F24C0000000806FC64A40000000E0DD6523C00000006088CC4A400000004012D023C0000000001AE14A40000000806E1F23C0000000400BEE4A40000000E0A2E123C0000000C017EF4A4000000060449423C00000004003F94A40000000C0DC0624C0000000A0ED1B4B40000000A0803F24C0000000005D0C4B4000000040753924C000000080701D4B400000002021F320C00000000001234B4000000000C65221C000000080792D4B40000000406D6020C0000000001A514B4000000040BF9821C0000000A00E594B400000000031B520C0000000C0726B4B400000002019EA20C000000020977F4B400000000002ED1FC0000000E0B49B4B400000000084CC1EC0000000602D8C4B4000000020BB2A1FC000000060239B4B4000000040AE871EC0000000A0FDA14B400000008077771EC0000000C0E5864B40000000C0AABA1EC000000000B7794B40000000C03EC91DC0000000E020874B4000000000A4301EC0000000C0C49B4B4000000000B5811DC0000000A0A3B04B400000004095BD1BC000000020869E4B400000004091021DC00000004009894B40000000409D361EC000000080A2614B40000000809FB41FC0000000A0AB594B40000000C046021FC0000000C0164C4B40000000C0EC5020C0000000E05A384B4000000040DF3C1EC0000000803F104B4000000000B4221DC0000000C0CD0F4B40000000C0261E1CC00000006067354B4000000080E17A1AC000000080C3044B4000000000621119C000000040C70C4B40", LW_PARSER_CHECK_NONE);
	p = lwgeom_as_lwpoly(g);
	lwpt = (LWPOINT*)lwgeom_from_hexwkb("0101000020E610000057B89C28FEB320C09C8102CB3B2B4A40", LW_PARSER_CHECK_NONE);
	lwpoint_getPoint2d_p(lwpt, &pt);
	lwgeom_calculate_gbox_geodetic(g, &gbox);
	gbox_pt_outside(&gbox, &pt_outside);
	//printf("OUTSIDE POINT(%g %g)\n", pt_outside.x, pt_outside.y);
	c = circ_tree_new(p->rings[0]);
	rv_classic = lwpoly_covers_point2d(p, &pt);
	rv_tree = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv_tree, rv_classic);
	circ_tree_free(c);
	lwpoint_free(lwpt);
	lwgeom_free(g);

	g = lwgeom_from_hexwkb("0103000020E610000001000000CF0100000000000000004EC03943F5FFFF7F56400000000000003E403943F5FFFF7F56400000000000003E401842CEFBFF7F56400000000000003E402F849CF7FF7F56400000000000003E4047C66AF3FF7F56400000000000003E405F0839EFFF7F56400000000000003E40774A07EBFF7F56400000000000003E408F8CD5E6FF7F56400000000000003E40A6CEA3E2FF7F56400000000000003E40D65240DAFF7F56400000000000003E4006D7DCD1FF7F56400000000000003E40355B79C9FF7F56400000000000003E407D21E4BCFF7F56400000000000003E40DC291DACFF7F56400000000000003E403B32569BFF7F56400000000000003E40CABE2B82FF7F56400000000000003E40594B0169FF7F56400000000000003E40309E4143FF7F56400000000000003E401E335019FF7F56400000000000003E403C4CFBE6FE7F56400000000000003E40B96DDFA3FE7F56400000000000003E407E552E54FE7F56400000000000003E40A245B6F3FD7F56400000000000003E403D80457EFD7F56400000000000003E407E8978EBFC7F56400000000000003E407FA31D37FC7F56400000000000003E405510035DFB7F56400000000000003E404A969350FA7F56400000000000003E40BC3D0801F97F56400000000000003E40C3482F6AF77F56400000000000003E40D5011077F57F56400000000000003E406CB3B112F37F56400000000000003E402C2CB81FF07F56400000000000003E40A4F8F884EC7F56400000000000003E40C5AD8218E87F56400000000000003E40C1A6CEA3E27F56400000000000003E40A1BAB9F8DB7F56400000000000003E40401361C3D37F56400000000000003E40639813B4C97F56400000000000003E408D429259BD7F56400000000000003E40B854A52DAE7F56400000000000003E406F9EEA909B7F56400000000000003E403FC6DCB5847F56400000000000003E408FC536A9687F56400000000000003E402975C938467F56400000000000003E403F8D7BF31B7F56400000000000003E40F4311F10E87E56400000000000003E40C1FBAA5CA87E56400000000000003E40D2FF722D5A7E56400000000000003E4009A7052FFA7D56400000000000003E403332C85D847D56400000000000003E40B35F77BAF37C56400000000000003E40253ACB2C427C56400000000000003E40FA7B293C687B56400000000000003E407D3D5FB35C7A56400000000000003E40E3A25A44147956400000000000003E40A0504F1F817756400000000000003E4062855B3E927556400000000000003E40B62BF4C1327356400000000000003E40280D350A497056400000000000003E4061DC0DA2B56C56400000000000003E40B81E85EB516856400000000000003E403237DF88EE6256400000000000003E4041EE224C515C56400000000000003E409EE925C6325456400000000000003E400B2593533B4A56400000000000003E4089CF9D60FF3D56400000000000003E40F04A92E7FA2E56400000000000003E40AC3594DA8B1C56400000000000003E40C9022670EB0556400000000000003E4069A510C825EA55400000000000003E4033DC80CF0FC855400000000000003E40FF907EFB3A9E55400000000000003E404203B16CE66A55400000000000003E40DA39CD02ED2B55400000000000003E4070404B57B0DE54400000000000003E4000000000008054403333333333B33D4000000000008054406666666666663D4000000000008054409999999999193D400000000000805440CCCCCCCCCCCC3C4000000000008054400000000000803C4000000000008054403333333333333C4000000000008054406666666666E63B4000000000008054409999999999993B400000000000805440CCCCCCCCCC4C3B4000000000008054400000000000003B4000000000008054403333333333B33A4000000000008054406666666666663A4000000000008054409999999999193A400000000000805440CCCCCCCCCCCC3940000000000080544000000000008039400000000000805440333333333333394000000000008054406666666666E63840000000000080544099999999999938400000000000805440CCCCCCCCCC4C38400000000000805440000000000000384000000000008054403333333333B3374000000000008054406666666666663740000000000080544099999999991937400000000000805440CDCCCCCCCCCC3640000000000080544000000000008036400000000000805440333333333333364000000000008054406666666666E63540000000000080544099999999999935400000000000805440CDCCCCCCCC4C35400000000000805440000000000000354000000000008054403333333333B3344000000000008054406666666666663440000000000080544099999999991934400000000000805440CDCCCCCCCCCC3340000000000080544000000000008033400000000000805440333333333333334000000000008054406666666666E63240000000000080544099999999999932400000000000805440CDCCCCCCCC4C32400000000000805440000000000000324000000000008054403333333333B3314000000000008054406666666666663140000000000080544099999999991931400000000000805440CDCCCCCCCCCC304000000000008054400000000000803040000000000080544033333333333330400000000000805440CCCCCCCCCCCC2F4000000000008054403333333333332F4000000000008054409999999999992E4000000000008054400000000000002E4000000000008054406666666666662D400000000000805440CCCCCCCCCCCC2C4000000000008054403333333333332C4000000000008054409999999999992B4000000000008054400000000000002B4000000000008054406666666666662A400000000000805440CCCCCCCCCCCC2940000000000080544033333333333329400000000000805440999999999999284000000000008054400000000000002840000000000080544066666666666627400000000000805440CDCCCCCCCCCC2640000000000080544033333333333326400000000000805440999999999999254000000000008054400000000000002540000000000080544066666666666624400000000000805440CDCCCCCCCCCC2340000000000080544033333333333323400000000000805440999999999999224000000000008054400000000000002240000000000080544066666666666621400000000000805440CDCCCCCCCCCC20400000000000805440333333333333204000000000008054403333333333331F4000000000008054400000000000001E400000000000805440CCCCCCCCCCCC1C4000000000008054409999999999991B4000000000008054406666666666661A4000000000008054403333333333331940000000000080544000000000000018400000000000805440CDCCCCCCCCCC1640000000000080544099999999999915400000000000805440666666666666144000000000008054403333333333331340000000000080544000000000000012400000000000805440CDCCCCCCCCCC104000000000008054403333333333330F400000000000805440CCCCCCCCCCCC0C4000000000008054406666666666660A400000000000805440000000000000084000000000008054409999999999990540000000000080544033333333333303400000000000805440CDCCCCCCCCCC00400000000000805440CCCCCCCCCCCCFC3F0000000000805440000000000000F83F0000000000805440333333333333F33F0000000000805440CCCCCCCCCCCCEC3F0000000000805440333333333333E33F0000000000805440333333333333D33F00000000008054400000000000000000000000000080544000000000000000002174D0251C7C54400000000000000000F96871C6307854400000000000000000E6E61BD13D745440000000000000000019726C3D437054400000000000000000F0129CFA406C54400000000000000000CCD1E3F7366854400000000000000000F374AE28256454400000000000000000ACC266800B6054400000000000000000700514EAE95B544000000000000000006EC1525DC057544000000000000000001C412AC58E5354400000000000000000AB083719554F5440000000000000000091628044134B544000000000000000001615713AC94654400000000000000000992842EA7642544000000000000000007AA52C431C3E5440000000000000000000529B38B939544000000000000000008B36C7B94D3554400000000000000000795BE9B5D9305440000000000000000029C93A1C5D2C54400000000000000000E54526E0D72754400000000000000000211CB3EC49235440000000000000000027124C35B31E5440000000000000000055302AA9131A544000000000000000000A7F86376B1554400000000000000000BE4868CBB91054400000000000000000A1116C5CFF0B54400000000000000000406667D13B0754400000000000000000E50CC51D6F0254400000000000000000ED0DBE3099FD53400000000000000000D0B359F5B9F853400000000000000000D6C4025FD1F353400000000000000000768BC058DFEE534000000000000000000E10CCD1E3E953400000000000000000FF5A5EB9DEE453400000000000000000A774B0FECFDF534000000000000000006665FB90B7DA53400000000000000000CBB9145795D55340000000000000000005F6984869D053400000000000000000BCE82B4833CB534000000000000000001E166A4DF3C553400000000000000000A3C85A43A9C053400000000000000000DA8CD31055BB53400000000000000000F3E670ADF6B5534000000000000000007C6308008EB053400000000000000000EC4CA1F31AAB534000000000000000008B69A67B9DA553400000000000000000E945ED7E15A0534000000000000000004CA8E0F0829A53400000000000000000431D56B8E5945340000000000000000045EF54C03D8F534000000000000000009BE447FC8A8953400000000000000000D2890453CD83534000000000000000004BE7C3B3047E5340000000000000000093895B053178534000000000000000000B79043752725340000000000000000012BEF737686C5340000000000000000036E50AEF726653400000000000000000EF3845477260534000000000000000009CC1DF2F665A53400000000000000000CC0BB08F4E5453400000000000000000DE1FEF552B4E53400000000000000000618A7269FC4753400000000000000000B45373B9C141534000000000000000006708C72C7B3B53400000000000000000D9B0A6B228355340000000000000000098D9E731CA2E53400000000000000000340F60915F2853400000000000000000F4177AC4E821534000000000000000007EC2D9AD651B534000000000000000003317B83CD61453400000000000000000A0A2EA573A0E5340000000000000000056F146E6910753400000000000000000B20B06D7DC0053400000000000000000457EFD101BFA524000000000000000008593347F4CF352400000000000000000191A4F0471EC5240000000000000000049D8B79388E552400000000000000000BA9C121093DE52400000000000000000E6B1666490D75240000000000000000059A4897780D0524000000000000000008CBE823463C9524000000000000000000D8D278238C2524000000000000000006B9C4D4700BB524000000000000000001D37FC6EBAB352400000000000000000B3E908E066AC52400000000000000000A4FE7A8505A5524000000000000000009544F641969D52400000000000000000FF05820019965240000000000000000070CFF3A78D8E52400000000000000000772D211FF486524000000000000000008B6A11514C7F52400000000000000000545568209677524000000000000000005F7AFB73D16F524000000000000000002424D236FE675240000000000000000033DFC14F1C6052400000000000000000317A6EA12B5852400000000000000000963FDF162C505240000000000000000008FEB7921D48524000000000000000000000000000405240999999999999C9BF0000000000405240999999999999D9BF0000000000405240333333333333E3BF0000000000405240999999999999E9BF0000000000405240000000000000F0BF0000000000405240333333333333F3BF0000000000405240666666666666F6BF0000000000405240999999999999F9BF0000000000405240CCCCCCCCCCCCFCBF000000000040524000000000000000C0000000000040524099999999999901C0000000000040524033333333333303C00000000000405240CDCCCCCCCCCC04C0000000000040524066666666666606C0000000000040524000000000000008C0000000000040524099999999999909C000000000004052403333333333330BC00000000000405240CCCCCCCCCCCC0CC000000000004052406666666666660EC0000000000040524000000000000010C00000000000405240CDCCCCCCCCCC10C0000000000040524099999999999911C0000000000040524066666666666612C0000000000040524033333333333313C0000000000040524000000000000014C00000000000405240CDCCCCCCCCCC14C0000000000040524099999999999915C0000000000040524066666666666616C0000000000040524033333333333317C0000000000040524000000000000018C00000000000405240CCCCCCCCCCCC18C0000000000040524099999999999919C000000000004052406666666666661AC000000000004052403333333333331BC000000000004052400000000000001CC00000000000405240CCCCCCCCCCCC1CC000000000004052409999999999991DC000000000004052406666666666661EC000000000004052403333333333331FC0000000000040524000000000000020C0000000000040524066666666666620C00000000000405240CDCCCCCCCCCC20C0000000000040524033333333333321C0000000000040524099999999999921C0000000000040524000000000000022C0000000000040524066666666666622C00000000000405240CDCCCCCCCCCC22C0000000000040524033333333333323C0000000000040524099999999999923C0000000000040524000000000000024C0000000000040524066666666666624C00000000000405240CDCCCCCCCCCC24C0000000000040524033333333333325C0000000000040524099999999999925C0000000000040524000000000000026C0000000000040524066666666666626C00000000000405240CDCCCCCCCCCC26C0000000000040524033333333333327C0000000000040524099999999999927C0000000000040524000000000000028C0000000000040524066666666666628C00000000000405240CCCCCCCCCCCC28C0000000000040524033333333333329C0000000000040524099999999999929C000000000004052400000000000002AC000000000004052406666666666662AC00000000000405240CCCCCCCCCCCC2AC000000000004052403333333333332BC000000000004052409999999999992BC000000000004052400000000000002CC000000000004052406666666666662CC00000000000405240CCCCCCCCCCCC2CC000000000004052403333333333332DC000000000004052409999999999992DC000000000004052400000000000002EC000000000004052406666666666662EC00000000000405240CCCCCCCCCCCC2EC000000000004052403333333333332FC000000000004052409999999999992FC0000000000040524000000000000030C0000000000040524033333333333330C0000000000040524066666666666630C0000000000040524099999999999930C00000000000405240CDCCCCCCCCCC30C0000000000040524000000000000031C0000000000040524033333333333331C0000000000040524066666666666631C0000000000040524099999999999931C00000000000405240CDCCCCCCCCCC31C0000000000040524000000000000032C0000000000040524033333333333332C0000000000040524066666666666632C0000000000040524099999999999932C00000000000405240CDCCCCCCCCCC32C0000000000040524000000000000033C0000000000040524033333333333333C0000000000040524066666666666633C0000000000040524099999999999933C00000000000405240CDCCCCCCCCCC33C0000000000040524000000000000034C0000000000040524000000000000034C0000000000080514000000000008043C00000000000C04F4000000000008045C00000000000404D4030116F9D7F8B45C00000000000404D408FA67A32FF9645C00000000000404D40BFB7E9CF7EA245C00000000000404D401E4DF564FEAD45C00000000000404D404E5E64027EB945C00000000000404D40AEF36F97FDC445C00000000000404D40DD04DF347DD045C00000000000404D403D9AEAC9FCDB45C00000000000404D406DAB59677CE745C00000000000404D40CC4065FCFBF245C00000000000404D40FC51D4997BFE45C00000000000404D405BE7DF2EFB0946C00000000000404D408BF84ECC7A1546C00000000000404D40EB8D5A61FA2046C00000000000404D401B9FC9FE792C46C00000000000404D407A34D593F93746C00000000000404D40AA454431794346C00000000000404D40DA56B3CEF84E46C00000000000404D4039ECBE63785A46C00000000000404D4069FD2D01F86546C00000000000404D40C8923996777146C00000000000404D40F8A3A833F77C46C00000000000404D405839B4C8768846C00000000000404D40884A2366F69346C00000000000404D40E7DF2EFB759F46C00000000000404D4017F19D98F5AA46C00000000000404D407686A92D75B646C00000000000404D40A69718CBF4C146C00000000000404D40062D246074CD46C00000000000404D40353E93FDF3D846C00000000000404D4095D39E9273E446C00000000000404D40C5E40D30F3EF46C00000000000404D40247A19C572FB46C00000000000404D40548B8862F20647C00000000000404D40B42094F7711247C00000000000404D40E3310395F11D47C00000000000404D4013437232712947C00000000000404D4073D87DC7F03447C00000000000404D40A2E9EC64704047C00000000000404D40027FF8F9EF4B47C00000000000404D40329067976F5747C00000000000404D409125732CEF6247C00000000000404D40C136E2C96E6E47C00000000000404D4021CCED5EEE7947C00000000000404D4050DD5CFC6D8547C00000000000404D40B0726891ED9047C00000000000404D40E083D72E6D9C47C00000000000404D403F19E3C3ECA747C00000000000404D406F2A52616CB347C00000000000404D40CEBF5DF6EBBE47C00000000000404D40FED0CC936BCA47C00000000000404D405E66D828EBD547C00000000000404D408E7747C66AE147C00000000000404D40BD88B663EAEC47C00000000000404D401D1EC2F869F847C00000000000404D404D2F3196E90348C00000000000404D40ACC43C2B690F48C00000000000404D40DCD5ABC8E81A48C00000000000404D403B6BB75D682648C00000000000404D406B7C26FBE73148C00000000000404D40CB113290673D48C00000000000404D40FB22A12DE74848C00000000000404D405AB8ACC2665448C00000000000404D408AC91B60E65F48C00000000000404D40E95E27F5656B48C00000000000404D4019709692E57648C00000000000404D407905A227658248C00000000000404D40A81611C5E48D48C00000000000404D4008AC1C5A649948C00000000000404D4038BD8BF7E3A448C00000000000404D4068CEFA9463B048C00000000000404D40C763062AE3BB48C00000000000404D40F77475C762C748C00000000000404D40560A815CE2D248C00000000000404D40861BF0F961DE48C00000000000404D40E6B0FB8EE1E948C00000000000404D4015C26A2C61F548C00000000000404D4000000000000049C00000000000404D400000000000E04CC0000000000040504000000000000053C000000000000053400000000000C052C000000000008053400000000000004EC000000000008054400000000000004EC03943F5FFFF7F5640", LW_PARSER_CHECK_NONE);
	p = lwgeom_as_lwpoly(g);
	lwpt = (LWPOINT*)lwgeom_from_hexwkb("0101000020E610000031B1F9B836A046C03C889D2974124E40", LW_PARSER_CHECK_NONE);
	lwpoint_getPoint2d_p(lwpt, &pt);
	lwgeom_calculate_gbox_geodetic(g, &gbox);
	gbox_pt_outside(&gbox, &pt_outside);
	//printf("OUTSIDE POINT(%g %g)\n", pt_outside.x, pt_outside.y);
	c = circ_tree_new(p->rings[0]);
	rv_classic = lwpoly_covers_point2d(p, &pt);
	rv_tree = circ_tree_contains_point(c, &pt, &pt_outside, 0, &on_boundary);
	CU_ASSERT_EQUAL(rv_tree, rv_classic);
	circ_tree_free(c);
	lwpoint_free(lwpt);
	lwgeom_free(g);

}


static void test_tree_circ_distance(void)
{
	LWGEOM *lwg1, *lwg2;
	CIRC_NODE *c1, *c2;
	SPHEROID s;
	double d1, d2, d3, d4, e1, e2;
	double threshold = 0.0;

	spheroid_init(&s, 1.0, 1.0);

	/* Ticket 5765 */
	/* Two very close segments (1.64m) with mid-line points */
	lwg1 = lwgeom_from_wkt("LINESTRING (-1.7485638876537 52.477970467863,-1.7485727216213 52.477970486617)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("LINESTRING (-1.7486648265496 52.477955848635,-1.7485639721184 52.477955634571)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	e1 = d1 * WGS84_RADIUS;
	e2 = d2 * WGS84_RADIUS;

	// printf("\nRadians (tree and brute force)\n");
	// printf("  d1 = %g r   d2 = %g r\n", d1, d2);
	// printf("\nMeters (tree and brute force)\n");
	// printf("  e1 = %g m   e2 = %g m\n\n", e1, e2);
	// printf("linestring a\n");
	// circ_tree_print(c1, 0);
	// printf("linestring b\n");
	// circ_tree_print(c2, 0);

	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(e1, e2, 0.0001);

	return;

	/* Ticket #4223 */
	/* tall skinny rectangle */
	lwg1 = lwgeom_from_wkt("POLYGON((58.5112113206308 0,58.5112113200772 0.000901937525203378,58.511300910044 0.000901937636668872,58.5113009105976 0,58.5112113206308 0))", LW_PARSER_CHECK_NONE);
	/* square box 5m to left */
	lwg2 = lwgeom_from_wkt("POLYGON((58.5111665256017 0.000270581240841207,58.5111665255629 0.000360774987788249,58.5110769356128 0.000360774943200728,58.5110769356515 0.000270581207400566,58.5111665256017 0.000270581240841207))", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	e1 = d1 * WGS84_RADIUS;
	e2 = d2 * WGS84_RADIUS;
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(e1, e2, 0.0001);


	/* Ticket #1958 */
	lwg1 = lwgeom_from_wkt("LINESTRING(22.88333 41.96667,21.32667 42.13667)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POLYGON((22.94472 41.34667,22.87528 41.99028,22.87389 41.98472,22.87472 41.98333,22.94472 41.34667))", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.0000001);

	/* Ticket #1951 */
	lwg1 = lwgeom_from_wkt("LINESTRING(0 0, 0 0)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT(0.1 0.1)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.00001);

	lwg1 = lwgeom_from_wkt("LINESTRING(-1 -1,0 -1,1 -1,1 0,1 1,0 0,-1 1,-1 0,-1 -1)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT(-2 0)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.00001);

	lwg1 = lwgeom_from_wkt("LINESTRING(-1 -1,0 -1,1 -1,1 0,1 1,0 0,-1 1,-1 0,-1 -1)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT(2 2)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.00001);

	lwg1 = lwgeom_from_wkt("LINESTRING(-1 -1,0 -1,1 -1,1 0,1 1,0 0,-1 1,-1 0,-1 -1)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT(1 1)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.00001);

	lwg1 = lwgeom_from_wkt("LINESTRING(-1 -1,0 -1,1 -1,1 0,1 1,0 0,-1 1,-1 0,-1 -1)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT(1 0.5)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
//	printf("distance_tree %g\n", distance_tree);
//	printf("distance_geom %g\n", distance_geom);
//	circ_tree_print(cline, 0);
//	circ_tree_print(cpoint, 0);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.00001);


	/* Ticket #2351 */
	lwg1 = lwgeom_from_wkt("LINESTRING(149.386990599235 -26.3567415843982,149.386990599247 -26.3567415843965)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT(149.386990599235 -26.3567415843982)", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
//	printf("d1 = %g   d2 = %g\n", d1 * WGS84_RADIUS, d2 * WGS84_RADIUS);
//	printf("line\n");
//	circ_tree_print(c1, 0);
//	printf("point\n");
//	circ_tree_print(c2, 0);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.0000001);

	/* Ticket #2634 */
	lwg1 = lwgeom_from_wkt("MULTIPOINT (-10 40,-10 65,10 40,10 65,30 40,30 65,50 40,50 65)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POLYGON((-9.1111111 40,-9.14954053919354 39.6098193559677,-9.26335203497743 39.2346331352698,-9.44817187539491 38.8888595339608,-9.6968975376269 38.5857864376269,-9.99997063396079 38.3370607753949,-10.3457442352698 38.1522409349774,-10.7209304559677 38.0384294391935,-11.1111111 38,-11.5012917440323 38.0384294391935,-11.8764779647302 38.1522409349774,-12.2222515660392 38.3370607753949,-12.5253246623731 38.5857864376269,-12.7740503246051 38.8888595339608,-12.9588701650226 39.2346331352698,-13.0726816608065 39.6098193559677,-13.1111111 40,-13.0726816608065 40.3901806440322,-12.9588701650226 40.7653668647302,-12.7740503246051 41.1111404660392,-12.5253246623731 41.4142135623731,-12.2222515660392 41.6629392246051,-11.8764779647302 41.8477590650226,-11.5012917440323 41.9615705608065,-11.1111111 42,-10.7209304559678 41.9615705608065,-10.3457442352698 41.8477590650226,-9.9999706339608 41.6629392246051,-9.69689753762691 41.4142135623731,-9.44817187539491 41.1111404660392,-9.26335203497743 40.7653668647302,-9.14954053919354 40.3901806440323,-9.1111111 40))", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
//	printf("d1 = %g   d2 = %g\n", d1 * WGS84_RADIUS, d2 * WGS84_RADIUS);
//	printf("multipoint\n");
//	circ_tree_print(c1, 0);
//	printf("polygon\n");
//	circ_tree_print(c2, 0);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.0000001);

	/* Ticket #2634 */
	lwg1 = lwgeom_from_wkt("MULTIPOINT Z (-10 40 1,-10 65 1,10 40 1,10 65 1,30 40 1,30 65 1,50 40 1,50 65 1,-10 40 2,-10 65 2,10 40 2,10 65 2,30 40 2,30 65 2,50 40 2,50 65 2,-10 40 3,-10 65 3,10 40 3,10 65 3,30 40 3,30 65 3,50 40 3,50 65 3)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("MULTIPOLYGON(((-9.1111111 40,-9.14954053919354 39.6098193559677,-9.26335203497743 39.2346331352698,-9.44817187539491 38.8888595339608,-9.6968975376269 38.5857864376269,-9.99997063396079 38.3370607753949,-10.3457442352698 38.1522409349774,-10.7209304559677 38.0384294391935,-11.1111111 38,-11.5012917440323 38.0384294391935,-11.8764779647302 38.1522409349774,-12.2222515660392 38.3370607753949,-12.5253246623731 38.5857864376269,-12.7740503246051 38.8888595339608,-12.9588701650226 39.2346331352698,-13.0726816608065 39.6098193559677,-13.1111111 40,-13.0726816608065 40.3901806440322,-12.9588701650226 40.7653668647302,-12.7740503246051 41.1111404660392,-12.5253246623731 41.4142135623731,-12.2222515660392 41.6629392246051,-11.8764779647302 41.8477590650226,-11.5012917440323 41.9615705608065,-11.1111111 42,-10.7209304559678 41.9615705608065,-10.3457442352698 41.8477590650226,-9.9999706339608 41.6629392246051,-9.69689753762691 41.4142135623731,-9.44817187539491 41.1111404660392,-9.26335203497743 40.7653668647302,-9.14954053919354 40.3901806440323,-9.1111111 40)))", LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
//	printf("\n");
//	circ_tree_print(c1, 0);
//	printf("\n");
//	circ_tree_print(c2, 0);
//	printf("\n");
	d1 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	d2 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d3 = circ_tree_distance_tree(c1, c2, &s, threshold);
	d4 = circ_tree_distance_tree(c1, c2, &s, threshold);
//	printf("\n d1-no-tree %20.20g\n d2 %20.20g\n d3 %20.20g\n d4 %20.20g\n", d1, d2, d3, d4);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, d2, 0.00000001);
	CU_ASSERT_DOUBLE_EQUAL(d1, d3, 0.00000001);
	CU_ASSERT_DOUBLE_EQUAL(d1, d4, 0.00000001);


	/* Ticket #4290 */
	const char *wkb1 = "0103000020E610000001000000EB010000560E7951F83853C0986D8DC811AE42404601F3C2F93853C028F9A6C80FAE42400EF46097FB3853C07B5CA9550FAE4240CC9BF16EFD3853C0F0D49BDC0FAE42400662BD42FF3853C03DF79F370FAE4240FC814915013953C0669AAA2E0EAE42401B6D54A7023953C0372CBC910CAE4240A451EF59043953C0336BCB570BAE42409C75E90B063953C08A26DAEB09AE42401554B6DF073953C04131DD4609AE4240F900D2D2093953C006A1DFA008AE424074706C850B3953C09198EB6607AE42401D7798580D3953C06B9AF28F06AE4240D75FC42B0F3953C0B5E9F6B805AE42409732F0FE103953C06600FBE104AE4240A0475DD3123953C0198EFA6E04AE4240B9805AC8143953C0AA9EF25E04AE42407E92B8BC163953C0E888EC1C04AE4240DA1615B1183953C0FBB7E8DA03AE4240184CE1841A3953C0B87CE93503AE42402370AD581C3953C07508EA9002AE4240B1483C301E3953C0247BD81703AE42405ECEE5321F3953C02740AB9905AE424008B91F18203953C0691E78B208AE42402245F374213953C07DE45A050AAE42408017844C233953C0E4A0488C0AAE4240005FE240253953C08116434A0AAE424029093F35273953C011DD3A080AAE4240DA0AAC09293953C0FBAA379509AE42403CA208FE2A3953C041F22E5309AE424033BED4D12C3953C090742DAE08AE4240E30392C52E3953C080D5283A08AE424020960D7A303953C080A2279607AE424068FB69AC323953C0F3911E2007AE4240A3059541343953C0F3B51D7D06AE4240B2CF6015363953C0FD161BD805AE424027B38BE8373953C079E51C0105AE424051CB55BC393953C06CE1195C04AE4240397D808F3B3953C08DC4188503AE424014BD5A433D3953C09BC41AAF02AE4240F98D76363F3953C0A52D160902AE4240A0E9410A413953C04739126401AE4240BA535A3B433953C0339C0D8A00AE4240000C95B0443953C0F58710B6FFAD4240C73EBF83463953C010170EDFFEAD4240EDDCF774483953C03D5111A3FDAD42400C5120484A3953C06C780ECCFCAD4240B8F7B7FA4B3953C0012C1392FBAD424011D740CD4D3953C046821489FAAD4240AF9BC99F4F3953C055A01580F9AD4240443CF372513953C0FBDC11A9F8AD4240D6CE1C46533953C0F95A10D2F7AD42405CB64419553953C026330CFBF6AD42402417CDEB563953C0C56F0CF2F5AD42400055B4BD583953C032A40EB7F4AD4240191E4B705A3953C078B9117DF3AD42401FF250025C3953C024881CE0F1AD4240131655945D3953C0813A2743F0AD424094704A465F3953C0C4F62BD7EEAD4240321FD218613953C0EDFA2ACEEDAD424017AB59EB623953C0EA4C27C5ECAD42403B24E1BD643953C0A6E025BCEBAD424081351871663953C0DC6D25B4EAAD4240EA11AE23683953C0DBFB267AE9AD4240743A35F6693953C0C5EE2471E8AD424020615DC96B3953C083FD1D9AE7AD424054EAF27B6D3953C06CF21E60E6AD42408606BC4F6F3953C0D36115BBE5AD4240183BA2E3703953C0AE0615B4E4AD4240B2EA1A98723953C048570C10E4AD42402E54006A743953C0583A0BD5E2AD4240C559951C763953C008380B9BE1AD4240F49F290D783953C038060D2DE0AD424025BF2B9F793953C0BD5C1290DEAD424002A610717B3953C0A7681055DDAD4240B1FE03237D3953C09E4B14E9DBAD42405E6798D57E3953C0805013AFDAAD42407DC73C68803953C033B41544D9AD42409343ED18823953C0BE721D74D7AD4240E7634DAA833953C066EA28A5D5AD4240DF7CCDFB843953C000F23874D3AD424085E94B4D863953C0F9634B43D1AD4240D6D3E85E873953C0017D67B0CEAD424065B12733883953C008167D83CCAD42406A881464893953C0B39497EFC9AD42409C16F1B48A3953C0B2DDAB8CC7AD42404B7ACD058C3953C0930AC029C5AD42402AFF4A578D3953C011E6D1F8C2AD42402D3037888E3953C0E201EC64C0AD42403D5DB4D98F3953C0B12DFB33BEAD42406D1950EB903953C0C8A216A1BBAD42400D889BDD913953C00C17310FB9AD4240E773B570923953C0D675591CB6AD4240F9CED003933953C0C0487F29B3AD4240B6B2CA14943953C028BE9C64B0AD42406EB34928953953C04056AC67AEAD42405F902479963953C0C7A5BF04ACAD4240522FAFAA973953C02B70D4A2A9AD4240BA954C7E983953C0A04EF043A7AD42404764A48E993953C0C59C0F4DA4AD4240B2ABEE809A3953C0228F29BBA1AD4240A10049539B3953C0FEB449F89EAD424080AAA1259C3953C0FEDC69359CAD4240321C4DD99C3953C0755889A599AD424030BB05AB9D3953C07396ABB096AD42409B990F5E9E3953C0A237CDEE93AD4240D40FD50F9F3953C0E64AF3C890AD4240324B90A39F3953C0B17616088EAD424032895817A03953C000883D168BAD4240B4FFB4ABA03953C0FD735E8788AD4240D4CD0F40A13953C08FED7CF885AD424060BB77F2A13953C0439EA00483AD42400D96DFA4A23953C053C1C61080AD424023602897A33953C0BC2CE07E7DAD4240A1AACF88A43953C09E3AFEBA7AAD4240068DD83BA53953C0C1901FF977AD42402556E1EEA53953C03DDF403775AD4240AB60AA62A63953C0A8B7674572AD42405D96D397A63953C0F0F491556FAD42400A935E8EA63953C0238CBF676CAD4240C9B6B671A63953C029C16D3E6BAD4240C2815AF3A53953C04C461B6269AD4240F7E145ABA53953C02EB84E7666AD4240878F2FA1A53953C0FE817E5663AD4240D6525AD6A53953C0F3B1A86660AD424046A3214AA63953C03E10D2745DAD4240E367EABDA63953C095E4F8825AAD42408BD54090A73953C0957B18C057AD4240353D5923A83953C036913DCD54AD4240AC72AFF5A83953C045165D0A52AD4240A942F8E7A93953C0261A76784FAD424012D10E7BAA3953C09C279B854CAD4240FBAE644DAB3953C06F8EBAC249AD424037CDCAFFAB3953C027D2DDCE46AD42405D2D4354AC3953C07AB608DE43AD42409529C7FFAC3953C075B49F9D41AD4240C07BAD14AD3953C0F90522123FAD42405A18380BAD3953C0369C4F243CAD424045502101AD3953C035E2810439AD42401DA0E774AD3953C08793A81236AD42408EAEEE27AE3953C05D89C95033AD4240401206BBAE3953C0C263EE5D30AD4240E30A7E0FAF3953C0EEBE166D2DAD4240C2C293A2AF3953C0E2173E7A2AAD4240C45CA935B03953C0BCF1628727AD4240B0F7AFE8B03953C09EC983C524AD42401864C57BB13953C01098A8D221AD4240D1AF99CCB23953C05FA5B96F1FAD4240026AF15DB43953C0C7DDBDA01DAD424016EAE8EFB53953C017C3BF031CAD4240A85E74A2B73953C022B6B8C91AAD42407E110D35B93953C06694B55E19AD42401F4264C6BA3953C0C19FBB8F17AD4240C39EC837BC3953C0A42AC38F15AD424003B05C49BD3953C0753BD9FC12AD42407E24443CBE3953C0EB50F19C10AD42404E4949EFBE3953C055140FDB0DAD4240AC5C9CC1BF3953C078722D180BAD424096DC3EB3C03953C0C2DF495408AD4240BA3E9385C13953C0491A689105AD4240FD8A2697C23953C00F4B80FE02AD4240070823C6C33953C0DB329DD4FFAC42407B0EC979C43953C02BFBBA44FDAC42400D54C96AC53953C05F5AD94EFAAC42407A97CD1DC63953C00249F98CF7AC42409C3EF190C63953C06D782169F4AC42406D7417C6C63953C00E514B79F1AC42407394DC39C73953C021BD7387EEAC4240A380EFCCC73953C0D4C49794EBAC42408BC6429FC83953C010A4B5D1E8AC4240ED2FB5F0C93953C04C15C0A0E6AC4240AC823622CB3953C0BE91D33EE4AC42401756FC54CC3953C0F384DD40E2AC424072E300C7CD3953C0B034E172E0AC42403982D95ACF3953C0176DD76BDFAC4240656AF22DD13953C022BAC494DEAC424097FB45BFD23953C0CAEAC5C5DCAC4240CEA409F2D33953C085CED1C7DAAC424024871C44D53953C04F11D9C8D8AC424052FB5A74D63953C00718F002D6AC4240E0CF4C47D73953C0B20A0B72D3AC424095902C78D83953C065371DDED0AC4240BFDB200ADA3953C00A731B41CFAC4240648B95DCDB3953C0B73C0C38CEAC42406550ADAFDD3953C0060DF860CDAC42408C03D462DF3953C0107EEA58CCAC42406D1C35D4E03953C01BA1EE58CAAC42407F610325E23953C007BCFBF5C7AC424070453AB8E33953C06584F4BCC6AC4240C7C9BE6AE53953C00685E882C5AC4240712F343DE73953C01F6BD579C4AC4240143C4B10E93953C05F57C2A2C3AC4240C35902E4EA3953C01462AAFDC2AC424049F3BAB7EC3953C004279258C2AC42407834158CEE3953C0D4FC74E5C1AC4240F8B5CD5FF03953C090C95E40C1AC42409158E432F23953C000204869C0AC42401B1368E5F33953C0FB803A2FBFAC42407AB0EB97F53953C081B12CF5BDAC4240B3D5A36BF73953C07C291350BDAC4240D68DB83EF93953C0ACB2FB78BCAC424097124734FB3953C0FBE9D39ABCAC424018E6A6F2FB3953C08955BA5CBDAC424051AB0417FC3953C054999EEBBEAC4240ACDE61A4FA3953C00A82A187C0AC42406D51DEF1F83953C005E5AFC1C1AC424031F8EB5FF73953C009D9B45EC3AC42400C11FBCDF53953C03111BCFBC4AC4240DF71083CF43953C033B3C098C6AC4240AC24268AF23953C045A9C904C8AC424067D6E016F13953C09862D06EC9AC424099E43286EF3953C07703D06FCBAC4240FF1B92D5ED3953C07C8ED13FCDAC42403D7F6104EC3953C0477CDEACCEAC4240EDD2B8CFEA3953C0752BE014D0AC424026866B00E93953C0B322E117D2AC42403B26C78DE73953C02740E2B3D3AC42404D3B241BE63953C0FEA7E54FD5AC4240F4E8D189E43953C0ACFAE31ED7AC42401C5ADFF7E23953C00147E9BBD8AC4240E400FA45E13953C09E61F027DAAC4240301B1694DF3953C047B9F993DBAC4240851C2302DE3953C0D109FC30DDAC4240317E1F90DC3953C02CE4F9FEDEAC424032055F1FDB3953C021ADF030E1AC42400B3F0D8ED93953C0694FF0FFE2AC4240E8D4AA1CD83953C06185EBFFE4AC4240583B48ABD63953C0301FE4FFE6AC42407272F419D53953C0E85AE3CEE8AC4240BC0AD2E7D33953C08758D5FEEAAC42408D904FB6D23953C00112C560EDAC4240117DCE84D13953C0B9A7B4C2EFAC424032B64B53D03953C03733A424F2AC4240A343D901CF3953C03AD89755F4AC424089BC57D0CD3953C0712687B7F6AC4240CA6EE37ECC3953C066A27AE8F8AC42403019516DCB3953C0791D637BFBAC42408A147D5ACA3953C074DF54AAFDAC42408A942D4AC93953C0054A36A100AD4240C7F7B9E7C73953C08FDE2D6004AD42403B4F27CEC63953C0274EF85907AD4240AF45811AC63953C075A0DAE909AD4240EB958F09C53953C0FD75C0AE0CAD424048D14755C43953C05D67A70C0FAD42408667F744C33953C063E68A0312AD4240A3DE5453C23953C0B1A16EC714AD424018496080C13953C0A018555817AD424070E1788DC03953C00B373DB819AD42402DCE965CBF3953C09D38294C1CAD4240FA99024BBE3953C007D410DF1EAD4240A4257D19BD3953C03EEFFE4021AD4240389A9AE8BB3953C0B2AEEAD423AD4240B6D714B7BA3953C0059CD83626AD42401C0C80A5B93953C0CEE7BFC928AD42402A42DCB3B83953C0B012A38D2BAD4240258D9A83B73953C088CC89532EAD42403F25A3B0B63953C0E3C26FE430AD4240CA891ABDB53953C019E25B1233AD42403E3776CBB43953C079D23ED635AD4240009C6F18B43953C045261E9838AD42407DE76865B33953C06F72FD593BAD4240B42162B2B23953C0E130DF1B3EAD4240BE634C1FB23953C081F2B70E41AD4240D60A358CB13953C0B135930144AD4240455E1019B13953C08E676A2547AD4240CCB305A4B03953C0EF4848B349AD4240F6ABEF10B03953C0057223A64CAD424025C8279DAF3953C067DDFC974FAD4240D89CAF48AF3953C0CB80D48852AD4240985D37F4AE3953C05DA8A97955AD4240BBE80EBFAE3953C023847F6958AD4240099C966AAE3953C07B22575A5BAD42401D70CEF6AD3953C0BB81304C5EAD42405BC00783AD3953C0F4D0093E61AD42405C4F0BD5AC3953C026ADCF8F65AD424083E84261AC3953C00101A98168AD4240D5FD7BEDAB3953C0DA4482736BAD42400DE66198AB3953C0560B5C326EAD42403516FBE5AA3953C0FCC3382671AD42402B09E452AA3953C0553F111974AD424052491BDFA93953C04881EA0A77AD42405FA50F6AA93953C083A8CA9879AD4240DBB6E9F6A83953C0F2259FBC7CAD424059D5D063A83953C098167AAF7FAD4240F55C09F0A73953C0F13D53A182AD42409746407CA73953C0CB6E2C9385AD424087AD28E9A63953C06ECB048688AD4240E0725F75A63953C0F4F4DD778BAD4240B44EA6E1A53953C089F9BA388EAD4240DD863B6DA53953C0F45296F890AD4240794332BAA43953C0D47977BA93AD4240E26B2A07A43953C05712567C96AD424003CD1074A33953C0ACD6306F99AD4240563707C1A23953C00A6E0F319CAD4240849CBDCEA13953C03E80F3C29EAD42406A5165FCA03953C027A3D385A1AD4240FEFF6929A03953C01779B816A4AD42404869C1379F3953C0902D9ADAA6AD4240E0AF18469E3953C0F0D37B9EA9AD4240D2EECC539D3953C0A9296230ACAD42406E9282619C3953C071EA45C2AEAD4240991D386F9B3953C0F1162C54B1AD424086649D5D9A3953C06C5811E7B3AD4240A3AC526B993953C09366F778B6AD4240EE904B3C983953C07501D5A2B9AD424039DFBD48973953C0325CBFD0BBAD4240AA002075963953C0D7E9A52FBEAD4240DAC4D482953953C02BBD8BC1C0AD42409E608990943953C053086F53C3AD42408F39FC5E933953C0D3135AB5C5AD4240F0F0614D923953C0EFBE3E48C8AD42402AAD243B913953C0561428A9CAAD4240B1159709903953C0BDDF120BCDAD42409D89F41F8E3953C02157F49ED0AD4240DD1885AE8C3953C04248E69ED2AD4240A90A075D8B3953C021DDD6CFD4AD42402740870B8A3953C079E8C400D7AD42401E22AABA883953C09E95B063D9AD42407056DB49873953C039D29F95DBAD4240DA6ECBD7853953C0C2C39563DDAD42408B0F5B66843953C0DEF08663DFAD4240530EF9D4823953C0AD177E32E1AD4240E62AE762813953C095AB7300E3AD4240012436B27F3953C054DE6BD0E4AD42408ABC823F7E3953C0625B636CE6AD42403E73E16E7C3953C066BD5E0BE8AD42401565EBFA7A3953C06CCD5C43E9AD4240E1BD6428793953C0AC67634CEAAD4240F5F3DD55773953C0C44F6755EBAD424055E1B582753953C0DA326D2CECAD42403B22EEAE733953C08F7D77D1ECAD424001EEC5DB713953C033697FA8EDAD42409CC23E09703953C0AE6F82B1EEAD42409C3B75356E3953C0B91C8C56EFAD42406CC54C626C3953C08F5E932DF0AD4240C48B76706A3953C08CE99637F1AD424006E24BDB683953C099879DDAF1AD4240E1CAC508673953C01D6B9FE3F2AD4240E2133E36653953C01D9DA3ECF3AD424048E46544633953C06748A6F6F4AD4240959C7EB0613953C0B33CA5FDF5AD4240A28455DD5F3953C0C0FAAAD4F6AD42405C478B095E3953C0E3B0B279F7AD4240D9FD61365C3953C09A83B550F8AD4240FE3DDB635A3953C0A15AB859F9AD4240CE9C42B1583953C0DFD9B293FAAD42408473ABFE563953C0D595AFCDFBAD42409AD3222C553953C0F9D8B1D6FCAD424009718B79533953C03C30AE10FEAD4240631F04A7513953C04780AD19FFAD424070F66AF44F3953C0927FA95300AE4240F16DE3214E3953C02E63A85C01AE42409D3D5A4F4C3953C0511BA76502AE424086FAD07C4A3953C02D15A86E03AE424029A1A6A9483953C04C8BA84504AE42403014BED7463953C05D6CA48005AE4240A1B844E5443953C0CCCAA75806AE42405759B950433953C0F8CFA52D07AE4240A2FE7F9D413953C062CFA43508AE4240049BA5E93F3953C07E51A30B09AE4240D9D2CCB93D3953C03CB0A0490AAE424002DCD4453C3953C0DFB498810BAE4240028599923A3953C0BD7C94890CAE4240638100E0383953C045DA8DC30DAE4240B98BC62C373953C0D7AD8BCB0EAE42405623ED3A353953C07D6088D50FAE4240078D1087333953C0358A85AB10AE4240747735D3313953C0F0EF848111AE4240FD4F79DF2F3953C078EF89F511AE42401CD1AC0B2E3953C0F5D28B9A12AE42400741E0372C3953C0707D8D3F13AE42400A5106462A3953C0FD3F8B4914AE4240B75ADA72283953C019D0872015AE42402B8F0D9F263953C051CC88C515AE42403977E1CB243953C0F464879C16AE424070CEB6F8223953C0523E837317AE4240F1ED1A46213953C012037AAD18AE42406B3B21941F3953C094606E191AAE4240A6EFE5E01D3953C0A6E166211BAE4240F9C8FA0E1C3953C0A09E5D5C1CAE4240B37CB07B1A3953C03FFE52951DAE42406D8864E8183953C0E14048CE1EAE42402D401B17173953C0BCB5393B20AE424051917E64153953C027272F7521AE4240130184B2133953C0923222E122AE4240CAA2E8FF113953C07636171B24AE424066F8DE6D103953C004C104B825AE4240B777E2BB0E3953C0324CF72327AE4240EA87D8290D3953C03E81E4C028AE424044AC3C770B3953C018CBD8FA29AE4240F6EB30E5093953C02EB7C5972BAE42408F0AD633083953C0ABDAB2352DAE424002FA2AA1063953C02606A4A02EAE42404ED11E0F053953C0AE73903D30AE4240BB12147D033953C074AB7CDA31AE4240EB3BA8EB013953C0DB9F66A933AE424039CB3D5A003953C0C95E507835AE42406EA6D1C8FE3853C0AD013A4737AE4240E355C636FD3853C0B69525E438AE424068D4C8C2FB3853C01581171C3AAE42403E445C31FA3853C05CAC00EB3BAE4240311AF19FF83853C035A2E9B93DAE424010B2E30DF73853C0FAA1D4563FAE42400FB4D77BF53853C0006CBFF340AE4240ED8B6AEAF33853C0FEF3A7C242AE4240DF7DDF98F23853C0100E89F344AE42406A161408F13853C03A196FF446AE42400894D897EF3853C0150A4E5849AE4240C6140C45EE3853C0508B35254BAE424044DA7EF3EC3853C0573816564DAE42408A6D0382EB3853C07F06F9554FAE4240652F95F0E93853C07E8CE02451AE4240BF9B689EE83853C0F26DC52353AE4240D910FA0CE73853C012A9ACF254AE424046087E9BE53853C0F4EA8EF256AE424007586FCBE33853C08F0F76C358AE4240BD93E279E23853C06FCD55F45AAE4240FED0A447E13853C0065F35245DAE424055620854E03853C0291E17525FAE424007307B02DF3853C0BC91F68261AE424051D17DD1DD3853C0BA1ECF1664AE424083A630BFDC3853C0FD1EAC7766AE42402981D4CCDB3853C0B2D7860969AE42400C7127BBDA3853C0DD175F9C6BAE42409A08CBC8D93853C030B2392E6EAE4240F7B01DB7D83853C0EECF11C170AE42406A3C70A5D73853C05755EC5373AE42400C9BC293D63853C0834EC4E675AE4240883C2562D53853C0A7CAA04878AE4240E892C66FD43853C0EDA678DA7AAE42404EEA283ED33853C0F0F9543C7DAE4240368E890CD23853C09C42319E7FAE424030F38BDBD03853C0D9440B3282AE4240DF71DDC9CF3853C09AC9E2C484AE424098FB2E7ACE3853C00EFBB78B87AE4240808E3F67CD3853C0CB8F98BA89AE424017254174CC3853C00009721A8CAE4240436C3263CB3853C0EF9949DF8EAE4240057FBDCCC93853C0ACED431E8FAE424091FA48EBC83853C0207A62318DAE42406547459BC93853C00C6D9A7589AE42403DFF116DCA3853C01975C78086AE4240C714705FCB3853C0733EF0EE83AE424008E42D13CC3853C06956165F81AE42406690DC24CD3853C083133FCC7EAE424023A4BC95CE3853C0DA29619A7CAE42405ABD4BE7CF3853C0961783697AAE4240D8F7BC78D13853C051319E9A78AE42401D3FDDEAD23853C0EF21B9CC76AE424023BB7A1CD43853C0F6D6DC6A74AE4240981CE8EED43853C0392707A871AE424093F044E1D53853C054D72C166FAE4240EACEF2B4D63853C0AA5050B76CAE4240D0495E87D73853C0EF8B7AF469AE424026A6A8DAD73853C072ADAD9F66AE4240C0F551B1D73853C056C2DE8063AE4240C3526E6CD73853C0C891FB8E61AE424023C21A02D83853C0E9E71C645FAE4240D2669AF7D83853C0693535CC5DAE4240EE32DAE8DA3853C0D77446905CAE42405C718A7BDC3853C04FB759255BAE424010B966ECDD3853C0C2747AF358AE4240899E13C0DE3853C085849D9456AE42405B9A7F92DF3853C0A24AC7D153AE4240BD371805E03853C0C338FA7B50AE4240E8A511FBDF3853C0DC4D2B5C4DAE42408987EC6EE03853C0E66A576A4AAE424015975641E13853C0732881A747AE4240071EB333E23853C09513A61545AE42402167AE26E33853C06AD9C8B542AE42400D9A28D9E33853C0C8ABF4C13FAE42406423438CE43853C0C1521E003DAE42406E935D3FE53853C00FF2473E3AAE4240125D76F2E53853C06396717C37AE424015C98003E73853C008BF9AB734AE42406E519E37E83853C0FBDFB11D33AE424055715AE8E93853C08D74CA4D31AE4240E6CC853AEB3853C0BA81E54E2FAE4240C97F518DEC3853C0DB4DFE812DAE42405BADDDDEED3853C096B31D512BAE4240C39418D3EE3853C0B07E3B5529AE42400AD53307F03853C0D2974FBB27AE4240C3950F3AF13853C00ACA6CBD25AE42408AA8B9CFF13853C022328D9223AE4240B1B39243F23853C0F7D3B8A020AE42400F123C55F33853C0BC8ADC0D1EAE424095D59447F43853C051EB027C1BAE4240F05D0FB9F53853C036D51C7C19AE4240FC4948EBF63853C075CB3B4C17AE4240CEB8609EF73853C05AA0648A14AE4240560E7951F83853C0986D8DC811AE4240";
	const char *wkb2 = "0103000020E610000001000000080000002CAFE119EF2F53C02D6D4097DFBE42400050FBE7F32F53C05A08B32BD9BE42402ED0C3E9E52F53C0132FFFAE9DBE424048885052FE2F53C0DE5D06256BBE42409534CFEF163053C07D170F98ADBE42402E72095F303053C025ECD50CEABE424059CE3A7C103053C0235393C114BF42402CAFE119EF2F53C02D6D4097DFBE4240";
	spheroid_init(&s, WGS84_MAJOR_AXIS, WGS84_MINOR_AXIS);
	lwg1 = lwgeom_from_hexwkb(wkb1, LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_hexwkb(wkb2, LW_PARSER_CHECK_NONE);
	c1 = lwgeom_calculate_circ_tree(lwg1);
	c2 = lwgeom_calculate_circ_tree(lwg2);
	d1 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
	d2 = circ_tree_distance_tree(c1, c2, &s, threshold);
	circ_tree_free(c1);
	circ_tree_free(c2);
	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	CU_ASSERT_DOUBLE_EQUAL(d1, 18358.866, 0.01);
	CU_ASSERT_DOUBLE_EQUAL(d2, 18358.866, 0.01);
}

static void test_tree_circ_distance_threshold(void)
{
	SPHEROID s;
	int i, j;
	int step = 10;

	const char *txt_poly1 = "0103000020E6100000010000000B0000000AA2F068F47651C0F7893DEB70B8454007ABD4C6D57651C000FB650799B84540C21AA2645A7651C011C24BA84AB8454089A9A325E87751C03314EB5453B74540AF9ED96BF57751C0BF9818F889B74540E936A498B47751C0690C87D1C5B74540F5386204DC7751C02FCA658F1AB8454077B65F7B657751C012C586EE37B845408C1862C5977751C00F17E41674B84540D4012F57357751C0AD3BC67E99B845400AA2F068F47651C0F7893DEB70B84540";
	const char *txt_poly2 = "0103000020E610000003000000B5000000E0D13F40187451C01A09009164BB4540771C07D8FA7351C04DBBEDB634BB45400D27D627A47351C070625C9386BB4540D691981FAD7351C02F382CCDFABA4540AA38FA85B97351C03AD3A8271CBB4540D211F0CBBE7351C027F11A8FD9BA4540839AE427EB7351C0BF97C6BBA3BA4540748967A4D47351C00C0037C970BA45408F182A0CF07351C0C050808070BA45405063F06DD27351C0681018D037BA4540E509D5C2EE7351C0B9429E0231BA4540EA39B20CCC7351C018FBB70F22BA454072DD47C8ED7351C04C992D5E0BBA4540934BDE09CE7351C04B17895ACFB94540F7AA9F1EF77351C04DE737D4DCB945400D217458DF7351C022324164B0B945408A2F53C4087451C0A7EC0972B1B9454091A02DF3FC7351C0077F0D388AB94540D9EA0152187451C02316A57280B9454023E37795F07351C09314E67D36B945408DD1866BFC7351C06A0A537214B945405F77D635DE7351C01C7B3C251EB945404785C336F27351C07D767383F1B8454043664E41C77351C0F499D9F3C2B84540DA5CD86FDC7351C0ECA943B295B845403A60B1A2AF7351C063B81C61AFB8454041469468AA7351C0B0727EE16AB845405ADF4611937351C0AA5D2634A3B84540D1BB958D917351C0086C6F1450B845408BBECFF4787351C008F3F4958EB845407F025FE0737351C0506C9F8057B845405A49EDDE5E7351C0AB88DA1B84B845402AAE2CB6767351C07ECC7AEB33B845406C3BCEFF557351C0D93C09506DB8454032C3D6B8577351C0CF4410B115B84540C47F5B30337351C08DCEBB6F7DB845400DC58DB4127351C0D68016845EB845409E0DC353E17251C05E161FDE94B84540D94A5CCDF87251C0D4A79022C3B745404B789041A97151C0D366245447B64540E229E50C7A7151C04864DEC059B645403CF020E75F7151C0C2341E664FB745404F6388C1807151C0BE100BDA2FB7454099DB3D97877151C0853918DE6CB74540080D2824137151C017385A8090B74540A380F14EE97051C0A517F62259B74540C9B0B8E1F47051C019014EF43DB7454075AB809D997051C023033EFC28B745401FCC6CFD3C7051C01778CC51B1B74540A5AFFD2A5E7051C08B7644232EB8454075947311FD7051C0EB4B7B9F09B8454007A084455D7151C065E676C6A7B845401CB4DA891A7151C096D19999D0B84540F9D410BC3E7151C08C3797C11CB945400CA63027017151C0640A96032BBA4540B07FB7D8897151C0B632805859BA454078D01A1FDD7151C0202711EE70B945405F3A6E8E627251C0932D32FE34BA4540B532341D277251C0DFA18E0392BA4540CD8E813B147251C0FEBBA2346EBA4540421F7F16F87151C0DEB93B76A3BA45403B2350A3D37151C0330AF75F99BA454077512147AC7151C0A628D5F117BB454011C9CE77507151C04CC4E1E705BB4540E6889885EE7051C0C45D89CDA8BA4540575D1B37B07051C0F883C0A0D7BA45408A0FB14B977051C01D328086A9BA454033A7D2839B7051C0EEC463DD22BA4540AFDC6C64DC7051C013983A6CE3B94540CC1E39AEE17051C076E753DD7BB94540F6E0B3BECA7051C070E459395BB94540E636719D447051C0CB5C78F2F8B845402D3B6C3AC76F51C08AFD07346AB945404080D345386F51C02EFB7C9465B94540B5BB47ED506F51C0B5742F4FC3B84540F4DAAD32326F51C03AE0604DCEB8454079D03A00286F51C0BFE416D692B84540E7EEF142456F51C026483D9219B84540556E7F645D6F51C06BA1A86620B845406BD12F44536F51C0F976E08663B84540D7BFD8077B6F51C0C500FD8E63B8454004DD9EC4816F51C0441D30FBDBB745403EE733710C6F51C05E6524F44EB74540BEEA42C14A6E51C0367C93EEDEB54540C84C8F841D6E51C0F035740AD0B54540F0B3122E316E51C09158039618B44540F5E629F8706E51C02FD3E2F726B44540533862949E6E51C015FA5534BBB34540C649D8EDEF6E51C02B5E6D6F80B345405D7B912E616F51C0DF4BA76B0EB2454072578CCFB76F51C0A22CCF6690B1454015A5C130647051C0F4EFF7540FB14540F1ACD1FA9D7051C0329CCCA94CB14540374504840E7151C04726DFC9B5B04540C4B031D7D97151C0FC7C331392B04540DC234455E77151C00A9F4A04B9B04540D1505DECCD7151C0D9351517EAB04540CDD86B5EF87151C004CB649085B1454099BE7DDB797151C037D42330B4B245400EA292D32C7151C0820E1DD8B4B24540ACE77E61257151C0EE15BF9BEBB245407AA945D2867151C0666E8B0F01B345404EE1C915D37151C04B6DD883B3B24540C58BDF35247251C0D3FB74C050B445403C06C143697251C0603A1C0D59B44540D2F9E6E6B07251C0BC16F1CCC7B44540E47B911C8D7251C0A95F88542AB5454047BC0FA6237251C031E8A2FB38B54540CAB1FB9FF87151C03B2BF41EF7B445404EBF18E8017251C09C164886A8B4454050CD38EBC67151C014E9B12709B54540B4C7E42DD37151C0FB5B1E864CB54540BECC9D27167251C0B37B1B12AEB545400643207D967251C048C2DBC1ACB5454039070923977251C0E6D50A2602B64540DDD41A1C2E7351C06156AFD91EB645402FAEBC26AD7251C06DB4F5FA28B64540E6498EEFD87251C06214C5327CB645400C5E024B2E7351C0CABD9E93B9B6454001F550AB447351C0FBAFC57D96B645405AE881CF3D7351C01917460EC7B64540695D4AA6607351C00D689CE284B64540C6299985517351C076C84855D3B645406625BA34747351C0E739BF479CB64540386A02DD607351C0D6534476E1B645400B69DB9F997351C0B8AC5ACD90B645400E3CF2EEAC7351C05979D2F9A1B645400FD99F71887351C03916C9ACFAB64540CA154DF19B7351C0CC4ECC370AB745403B8F39FFC07351C0311B27F4ACB6454008ED94DBD07351C069128CC9B9B64540BDEC1CCDAA7351C0FA1AAC0617B74540A99C51C1C07351C07759CE3A2AB7454073FCF177E67351C04A84EAA2CDB6454055CDCB6ED17351C0CB6C7B6438B74540DDD31435F87351C0D4D993891FB74540811059D30D7451C077753AD162B74540F18AF9E46B7451C0FD21E09762B74540F253FA4F547451C067E3343FACB74540F0BCC760697451C0E0AE673BDBB74540FA1616AB497451C0D50836ABF0B74540F41845176E7451C0950B89B7FCB74540A16098ED3D7451C0D4E3E2D80BB84540B9AFBD7B727451C019895C361DB84540163C14EB717451C013C465C245B845402645A98E427451C049F426523FB84540C47E7169707451C0958552ED5DB84540652934E8467451C0D6A4B9DC6EB84540762DC58E717451C0F00F358EA7B8454052BD47144E7451C0CE25A2A9B7B84540FE28AFF55E7451C0EC20702D0BB94540DC47DC52777451C0DB556D5401B945407C974EEE617451C0DF8FB3BF25B94540F486D9A77E7451C0C20621B41AB94540432A3030707451C08AB2EDBC39B945409B0D7D28167551C0BB2B0598F9B84540E9C3E5D1067551C0617DD7107BB94540ADD4816DC57451C052E51C9E7FB9454083A85A09D37451C04AA52729AAB94540E8B74A52A57451C0054656858DB94540C1F58C11C07451C073982E6DC8B945406639F493967451C09D31BA6A90B9454023779107AB7451C026DD7171DFB945404CC088A46D7451C00324607A78B94540B4263081827451C0AF743013AAB94540A1FEA7A25A7451C030846A958DB945403B797701697451C00240A15CE1B945405EBCC1C4497451C0AF0092E9BCB945408A96E72B6A7451C0A85FF698F9B9454048855507427451C06852C7B9F0B94540CFBB01EA5C7451C0DC68FBB715BA4540D42EA3CF3C7451C0D2A6746A0BBA4540510413EB577451C0EE883A7D2CBA4540DC8C76E73B7451C0808E628128BA4540904E729D4F7451C09335C2C358BA4540A9018BEC347451C0017C60D031BA4540508873A32E7451C03F4C9200BDBA45400FEFB0B0567451C00274F969CCBA45402E2B3AC7317451C09C029279CBBA4540C6748AB7417451C060364B9C0EBB4540E0D13F40187451C01A09009164BB4540080000006DABE362BF6F51C03B3EAB0286B84540F2EBCFEEAC6F51C008D8984EA3B84540FF2B5394BB6F51C0B2F08C42CBB84540FDF9E71CFC6F51C07C7C0453C8B845403ABCCFEBCF6F51C0D477C34AC2B845402D81685DC76F51C071D8F5EE94B84540FB229C95E86F51C0BD8E7FF7AEB845406DABE362BF6F51C03B3EAB0286B8454008000000DB185B503E7051C066B728BCD3B245400AC83B92357051C04BA0208DA3B34540D7FCFFA31D7051C0CF7C254CD6B345400E29CDB9907051C012EB7D78CCB34540806300429F7051C0B0D493C19CB34540786CA34E6C7051C093B0BB4060B345407D77C1F9657051C0497CC614C3B24540DB185B503E7051C066B728BCD3B24540";
	const char *polys[2];
	static int npolys = 2;

	polys[0] = txt_poly1;
	polys[1] = txt_poly2;

	// spheroid_init(&s, WGS84_RADIUS, WGS84_RADIUS);
	spheroid_init(&s, WGS84_MAJOR_AXIS, WGS84_MINOR_AXIS);

	for ( j = 0; j < npolys; j++ )
	{
		LWGEOM *lwg1 = lwgeom_from_hexwkb(polys[j], LW_PARSER_CHECK_NONE);
		LWGEOM *lwg2 = lwgeom_from_wkt("POINT(-69.83262 43.43636)", LW_PARSER_CHECK_NONE);

		CIRC_NODE *c1 = lwgeom_calculate_circ_tree(lwg1);
		CIRC_NODE *c2 = lwgeom_calculate_circ_tree(lwg2);

		for ( i = 50; i < 1500 / step; i++ )
		{
			double d1, d2;
			double d = lwgeom_distance_spheroid(lwg1, lwg2, &s, 0);
			double threshold = step * i;
			d1 = circ_tree_distance_tree(c1, c2, &s, threshold);
			d2 = lwgeom_distance_spheroid(lwg1, lwg2, &s, threshold);
			if (threshold > d && (d1 > threshold || d2 > threshold))
			{
				printf("polygon #%d\n"
		       "threshold = %g\n"
					"true distance = %g\n"
		       "circ_tree_distance = %g\n"
		       "lwgeom_distance_spheroid = %g\n", j, threshold, d, d1, d2);
				CU_FAIL_FATAL();
			}
		}

		circ_tree_free(c1);
		circ_tree_free(c2);
		lwgeom_free(lwg1);
		lwgeom_free(lwg2);
	}

}

/***** Tests for IntervalTree *****/

static void test_itree_once(
	const char *polyWkt, double x, double y,
	IntervalTreeResult iexp)
{
	LWPOINT *pt = lwpoint_make2d(SRID_DEFAULT, x, y);
	LWGEOM *poly = lwgeom_from_wkt(polyWkt, LW_PARSER_CHECK_NONE);
	if(!poly)
		CU_FAIL_FATAL("unable to parse WKT");
	IntervalTree *itree = itree_from_lwgeom(poly);
	IntervalTreeResult irslt = itree_point_in_multipolygon(itree, pt);
	itree_free(itree);
	lwgeom_free(poly);
	lwpoint_free(pt);
	CU_ASSERT_EQUAL(irslt, iexp);
}

static void test_itree_square(void)
{
	const char *wktPoly =
		"MULTIPOLYGON(((-1 -1, 0 -1, 1 -1, 1 0, 1 1, -1 1, -1 -1)))";

	/* inside square */
	test_itree_once(wktPoly, 0.5, 0.5, ITREE_INSIDE);
	/* inside square at vertex */
	test_itree_once(wktPoly, 0.0, 0.0, ITREE_INSIDE);
	/* left of square */
	test_itree_once(wktPoly, -3.0, 0.0, ITREE_OUTSIDE);
	/* right of square */
	test_itree_once(wktPoly, 3.0, 0.0, ITREE_OUTSIDE);
	/* above square */
	test_itree_once(wktPoly, 0.0, 3.0, ITREE_OUTSIDE);
	/* on horizontal boundary */
	test_itree_once(wktPoly, 0.0, 1.0, ITREE_BOUNDARY);
	/* on vertical boundary */
	test_itree_once(wktPoly, -1.0, 0.0, ITREE_BOUNDARY);
}

static void test_itree_hole(void)
{
	const char *wktPoly =
		"POLYGON("
		"(-10 -10, 0 -10, 10 -10, 10 0, 10 10, 0 10, -10 10, -10 -10),"
		"(-5 -5, -5 0, -5 5, 5 5, 5 0, 5 -5, -5 -5))";

	/* inside hole */
	test_itree_once(wktPoly, 1.0, 1.0, ITREE_OUTSIDE);
	/* inside hole at vertical vertex */
	test_itree_once(wktPoly, 0.0, 0.0, ITREE_OUTSIDE);
	/* left of hole */
	test_itree_once(wktPoly, -7.0, 0.0, ITREE_INSIDE);
	/* right of hole */
	test_itree_once(wktPoly, 7.0, 0.0, ITREE_INSIDE);
	/* left of hole at top edge */
	test_itree_once(wktPoly, -7.0, 5.0, ITREE_INSIDE);
	/* right of hole at bottom edge */
	test_itree_once(wktPoly, 7.0, -5.0, ITREE_INSIDE);
	/* above hole */
	test_itree_once(wktPoly, 0.0, 7.0, ITREE_INSIDE);
	/* on hole boundary */
	test_itree_once(wktPoly, 0.0, 5.0, ITREE_BOUNDARY);
	/* on hole corner */
	test_itree_once(wktPoly, 5.0, 5.0, ITREE_BOUNDARY);
}

static void test_itree_hole_spike(void)
{
	const char *wktPoly =
		"POLYGON("
		"(-10 -10, 6 -10, 7 -10, 7.5 2, 8 -10, 9 -10, 10 -10, 10 10, -10 10, -10 2, -10 2, -10 -10),"
		"(-5 -5, -5 5, 5 5, 5 -5, -5 -5))";

	/* inside hole */
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);
	/* inside hole */
	test_itree_once(wktPoly, -2.0, -2.0, ITREE_OUTSIDE);
	/* left of spike */
	test_itree_once(wktPoly, 6.0, -2.0, ITREE_INSIDE);
	/* right of spike */
	test_itree_once(wktPoly, 9.0, -2.0, ITREE_INSIDE);
	/* left of tip of spike */
	test_itree_once(wktPoly, 6.0, 2.0, ITREE_INSIDE);
	/* right of tip of spike */
	test_itree_once(wktPoly, 9.0, 2.0, ITREE_INSIDE);
	/* on spike tip */
	test_itree_once(wktPoly, 7.5, 2.0, ITREE_BOUNDARY);
	/* left of dupe vertex */
	test_itree_once(wktPoly, -11, 2.0, ITREE_OUTSIDE);
	/* right of dupe vertex */
	test_itree_once(wktPoly, 11, 2.0, ITREE_OUTSIDE);
}

static void test_itree_multipoly_empty(void)
{

	/* outside empty */
	const char *wktPoly = "POLYGON EMPTY";
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);

	/* outside empty */
	wktPoly = "MULTIPOLYGON EMPTY";
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);

	/* outside collection of empty */
	wktPoly = "MULTIPOLYGON(EMPTY, EMPTY, EMPTY)";
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);

	/* mixed collection of empty and not */
	wktPoly =
		"MULTIPOLYGON(EMPTY,"
		"((-10 -10, 6 -10, 7 -10, 7.5 2, 8 -10, 9 -10, 10 -10, 10 10, -10 10, -10 2, -10 2, -10 -10),"
		"(-5 -5, -5 5, 5 5, 5 -5, -5 -5)))";

	/* inside hole */
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);
	/* inside hole */
	test_itree_once(wktPoly, -2.0, -2.0, ITREE_OUTSIDE);
	/* left of spike */
	test_itree_once(wktPoly, 6.0, -2.0, ITREE_INSIDE);
	/* right of spike */
	test_itree_once(wktPoly, 9.0, -2.0, ITREE_INSIDE);
	/* left of tip of spike */
	test_itree_once(wktPoly, 6.0, 2.0, ITREE_INSIDE);
	/* right of tip of spike */
	test_itree_once(wktPoly, 9.0, 2.0, ITREE_INSIDE);
	/* on spike tip */
	test_itree_once(wktPoly, 7.5, 2.0, ITREE_BOUNDARY);
	/* left of dupe vertex */
	test_itree_once(wktPoly, -11, 2.0, ITREE_OUTSIDE);
	/* right of dupe vertex */
	test_itree_once(wktPoly, 11, 2.0, ITREE_OUTSIDE);

	/* mixed collection of empty, empty in middle */
	wktPoly =
		"MULTIPOLYGON("
		"((-10 -10, 6 -10, 7 -10, 7.5 2, 8 -10, 9 -10, 10 -10, 10 10, -10 10, -10 2, -10 2, -10 -10),"
		"(-5 -5, -5 5, 5 5, 5 -5, -5 -5)),"
		"EMPTY, ((-1 -1, 1 -1, 1 1, -1 1, -1 -1)))";

	/* inside poly in hole */
	test_itree_once(wktPoly, 0.0, 0.0, ITREE_INSIDE);
	/* inside hole */
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);
	/* inside hole */
	test_itree_once(wktPoly, -2.0, -2.0, ITREE_OUTSIDE);
	/* left of spike */
	test_itree_once(wktPoly, 6.0, -2.0, ITREE_INSIDE);
	/* right of spike */
	test_itree_once(wktPoly, 9.0, -2.0, ITREE_INSIDE);
	/* left of tip of spike */
	test_itree_once(wktPoly, 6.0, 2.0, ITREE_INSIDE);
	/* right of tip of spike */
	test_itree_once(wktPoly, 9.0, 2.0, ITREE_INSIDE);
	/* on spike tip */
	test_itree_once(wktPoly, 7.5, 2.0, ITREE_BOUNDARY);
	/* left of dupe vertex */
	test_itree_once(wktPoly, -11, 2.0, ITREE_OUTSIDE);
	/* right of dupe vertex */
	test_itree_once(wktPoly, 11, 2.0, ITREE_OUTSIDE);
}

static void test_itree_degenerate_poly(void)
{
	/* collapsed polygon */
	const char *wktPoly = "POLYGON((0 0, 0 0, 0 0, 0 0))";
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);

	/* zero area polygon */
	wktPoly = "POLYGON((0 0, 0 1, 0 1, 0 0))";
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);
	test_itree_once(wktPoly, 0, 0.5, ITREE_BOUNDARY);
	test_itree_once(wktPoly, 0, 1, ITREE_BOUNDARY);

	/* zero area polygon */
	wktPoly = "POLYGON((0 0, 0 1, 1 1, 2 2, 1 1, 0 1, 0 0))";
	test_itree_once(wktPoly, 0.5, 0.5, ITREE_OUTSIDE);
	test_itree_once(wktPoly, 1, 1, ITREE_BOUNDARY);

	/* non finite coordinates */
	wktPoly = "POLYGON((0 0, 0 NaN, 0 NaN, 0 0, 0 1, 0 0))";
	test_itree_once(wktPoly, 2.0, 2.0, ITREE_OUTSIDE);
	test_itree_once(wktPoly, 0, 0, ITREE_BOUNDARY);
}


static void test_geography_tree_closestpoint(void)
{
	LWGEOM *lwg1, *lwg2, *lwg3;
	LWPOINT *lwpt;
	POINT2D pt;

	/* Simple case */
	lwg1 = lwgeom_from_wkt("LINESTRING (18 9, 18 1)", LW_PARSER_CHECK_NONE);
	lwg2 = lwgeom_from_wkt("POINT (16 4)", LW_PARSER_CHECK_NONE);
	lwg3 = geography_tree_closestpoint(lwg1, lwg2, 0.1);
	lwpt = (LWPOINT *)lwg3;

	lwpoint_getPoint2d_p(lwpt, &pt);
	CU_ASSERT_DOUBLE_EQUAL(pt.x, 18, 0.0001);
	CU_ASSERT_DOUBLE_EQUAL(pt.y, 4.0024302, 0.0001);

	lwgeom_free(lwg1);
	lwgeom_free(lwg2);
	lwgeom_free(lwg3);
}

/*
** Used by test harness to register the tests in this file.
*/
void tree_suite_setup(void);
void tree_suite_setup(void)
{
	CU_pSuite suite = CU_add_suite("spatial_trees", NULL, NULL);
	PG_ADD_TEST(suite, test_itree_square);
	PG_ADD_TEST(suite, test_itree_hole);
	PG_ADD_TEST(suite, test_itree_hole_spike);
	PG_ADD_TEST(suite, test_itree_multipoly_empty);
	PG_ADD_TEST(suite, test_itree_degenerate_poly);
	PG_ADD_TEST(suite, test_tree_circ_create);
	PG_ADD_TEST(suite, test_tree_circ_pip);
	PG_ADD_TEST(suite, test_tree_circ_pip2);
	PG_ADD_TEST(suite, test_tree_circ_distance);
	PG_ADD_TEST(suite, test_tree_circ_distance_threshold);
	PG_ADD_TEST(suite, test_geography_tree_closestpoint);
}
